﻿// Quad Tiling POJ - 3420.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>


using namespace std;

//https://vjudge.csgrandeur.cn/problem/POJ-3420

/*
游戏简介

迈克尔终于厌倦了 "三张牌 "游戏，转而玩起了更具挑战性的 "四张牌 "游戏：

在一个 4 × N（1 ≤ N ≤ 109）的矩形上，你能用多少种方法铺上 2 × 1 的多米诺骨牌？如果答案很大，请输出答案的模数 M（0 < M ≤ 10^5）。

输入

每个测试用例分别由两个整数 N 和 M 组成。

输出

输出每个测试用例的答案模块 M。

输入示例

1 10000
3 10000
5 10000
0 0
样本输出
1
11
95
*/



//const int N = 1000000010;
//int dp[2][1<<4];
//int stateHash[1 << 4];
//int n, MOD;
//
//void solve() {
//	memset(dp,0,sizeof dp);
//	
//	
//	for (int i = 0; i < 1 << 4; i++) {
//		bool cnt = 0, has_odd = 0;
//		for (int j = 0; j < 4; j++) {
//			if (i >> j & 1) {
//				//当前数位为1  
//				has_odd |= cnt, cnt = 0;
//			}
//			else {
//				//当前数位为0  记录连续系数  单个的1 3 5 7 则cnt异或1
//				//只记录有连续的0  1个为1 2个为0  3个为1 4个为0
//				cnt ^= 1;
//			}
//		}
//		if ( (cnt | has_odd) == 0) stateHash[i] = 1;
//	}
//
//	dp[0][0] = 1;
//	int curr = 1; int prev = 0;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 0; j < 1 << 4; j++) {
//			dp[curr][j] = 0;
//			for (int k = 0; k < 1 << 4; k++) {
//				if((j&k)==0 && stateHash[j|k])
//					dp[curr][j] += dp[prev][k], dp[curr][j] %= MOD;
//			}
//		}
//		swap(curr, prev);
//	}
//	
//	cout << dp[prev][0] << endl;
//}
//
//int main()
//{
//	while (cin >> n >> MOD) {
//		if (0 == n || 0 == MOD) { break; }
//		solve();
//	}
//
//	return 0;
//}
 

int main() {


	return 0;
}